Trivial Graph Format

Trivial Graph Format (TGF) is a simple text-based file format for describing graphs. It consists of a list of node definitions, which map node IDs to labels, followed by a list of edges, which specify node pairs and an optional edge label. Node IDs can be arbitrary identifiers, whereas labels for both nodes and edges are plain strings.

The graph may be interpreted as a directed or undirected graph. For directed graphs, to specify the concept of bidirectionality in an edge, one may either specify two edges (forward and back), or differentiate the edge by means of a label. For more powerful specification of graphs, see the other graph file formats below.

Contents

Example

A simple graph with 2 nodes and 1 edge might look like this:

1 First node
2 Second node
#
1 2 Edge between the two

Ease of use

TGF is useful for easily importing arbitrary data into a graph manipulation tool such as yEd. Because of the simplicity of the format, it is straightforward to use small programs or scripts to convert domain-specific data to this general format. For example, given a Makefile like this:

myprogram: myprogram.o libmytools.so
    gcc -L. -lmylib -o $@ $<

myprogram.o: myprogram.c
    gcc -c -o $@ $<

libmytools.so: mytools1.o mytools2.o
    gcc -shared -o $@ $<

mytools1.o: mytools1.c
    gcc -c -o $@ $<

mytools2.o: mytools2.c
    gcc -c -o $@ $<

clean:
    rm myprogram myprogram.o libmytools.so mytools1.o mytools2.o

It is possible to use a simple script, such as the following Python program, to turn the Makefile dependencies into TGF output:

#!/usr/bin/python
 
import fileinput, re
 
depends = {}
for line in fileinput.input():
    m = re.match('(.+):\s*(.*)',line) # find every depenency line of the form "<item>: <dependencies>"
    if m:
        item = m.group(1)
        dependency_list = m.group(2)
        print item,item # node definition
 
        if dependency_list: # there are dependencies
            depends[item] = dependency_list.split() # store the list into a dictionary for later
 
print "#" # end of node list, start of edge list
 
for item in depends:
    for dependency in depends[item]:
        print item,dependency # edge definition

This will produce a TGF graph which can then be visualized and analyzed using a graph manipulation tool. The above content yields the following graph:

Other Graph File Formats

See also

External links